import java.util.LinkedList;

// describes map, lands, moveable, etc.
class Map {
    private final Land[][] map; // size of N*N
    private final int size;

    // initialize map, return the positions of characters
    // Characters initial positions: {monsterX, monsterY, rogueX, rogueY}
    public Map(Input reader, int[] initialPositions, char[] monsterName) {
        size = reader.readInt();
        map = new Land[size][size];
        for (int y = size - 1; y >= 0; y--) { // row iteration
            String s = reader.readLine();
            for (int x = 0; x < size; x++) { // land iteration
                char c = s.charAt(x * 2);
                if (c == ' ' || c == '.' || c == '+') map[x][y] = new Land(c);
                else {
                    map[x][y] = new Land('.');
                    if (c == '@') {
                        initialPositions[2] = x;
                        initialPositions[3] = y;
                    } else {
                        monsterName[0] = c;
                        initialPositions[0] = x;
                        initialPositions[1] = y;
                    }
                }
            }
        }
    }

    private Map(Land[][] map) {
        size = map.length;
        this.map = new Land[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                this.map[i][j] = map[i][j].copy();
            }
        }
    }

    // return all neighbors
    public LinkedList<int[]> getNeighbors(int[] pos) {
        return getNeighbors(pos[0], pos[1]);
    }

    public LinkedList<int[]> getNeighbors(int x, int y) {
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (isDirectionMoveable(x, y, i, j)) list.add(new int[]{x + i, y + j});
            }
        }
        return list;
    }

    public int[] findDirection(int[] from, int[] to) {
        return new int[]{Integer.compare(to[0], from[0]), Integer.compare(to[1], from[1])};
    }

    // return all orthogonal neighbors
    public LinkedList<int[]> getOrthogonalNeighbors(int[] pos) {
        LinkedList<int[]> list = new LinkedList<>();
        int[][] directions = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};
        for (int[] dir : directions) {
            if (isDirectionMoveable(pos, dir)) list.add(new int[]{pos[0] + dir[0], pos[1] + dir[1]});
        }
        return list;
    }

    // return surrounding lands of type
    public LinkedList<int[]> getWallNeighbors(int[] pos) {
        LinkedList<int[]> result = new LinkedList<>();

        // orthogonal neighbors
        int[][] directions = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int[] dir : directions) {
            int[] land = new int[]{pos[0] + dir[0], pos[1] + dir[1]};
            if (land[0] >= 0 && land[0] < size && land[1] >= 0 && land[1] < size) {
                if (getType(land) == ' ') result.add(land);
            }
        }

        // diagonal neighbors
        directions = new int[][]{{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
        for (int[] dir : directions) {
            int[] land = new int[]{pos[0] + dir[0], pos[1] + dir[1]};
            if (land[0] >= 0 && land[0] < size && land[1] >= 0 && land[1] < size) {
                if (getType(land) == ' ')
                    if (getType(pos[0], land[1]) != '.' || getType(land[0], pos[1]) != '.') // diagonal wall
                        result.add(land);
            }
        }
        return result;
    }

    // whether a point at x,y can move in direction (moveX, moveY)
    public boolean isDirectionMoveable(int[] position, int[] direction) {
        return isDirectionMoveable(position[0], position[1], direction[0], direction[1]);
    }

    public boolean isDirectionMoveable(int x, int y, int moveX, int moveY) {
        int xnew = x + moveX;
        int ynew = y + moveY;
        if (xnew < 0 || xnew >= size || ynew < 0 || ynew >= size) return false; // reach boundary
        if (moveX == 0 || moveY == 0) // perpendicular movement
            return map[x][y].orthogonalMoveable(map[x + moveX][y + moveY]);
        return map[x][y].diagonalMoveable(map[x + moveX][y + moveY]);
    }

    // whether a point is at boundary
    public boolean isBoundary(int[] pos) {
        return pos[0] == 0 || pos[0] == size - 1 || pos[1] == 0 || pos[1] == size - 1;
    }


    // getters and basic methods
    public int size() {
        return size;
    }

    public char getType(int[] pos) {
        return getType(pos[0], pos[1]);
    }

    public char getType(int x, int y) {
        return map[x][y].getType();
    }

    public void setLand(int x, int y, char c) {
        if (x >= 0 && x < size && y >= 0 && y < size) map[x][y] = new Land(c);
    }

    public Map copy() {
        return new Map(map);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int y = size - 1; y >= 0; y--) {
            for (int x = 0; x < 2 * size - 1; x++) {
                if (x % 2 == 0) {
                    sb.append(getType(x / 2, y));
                } else {
                    sb.append(" ");
                }
            }
            sb.append(System.lineSeparator());
        }
        return sb.toString();
    }


    // nested class
    private static class Land {
        private final boolean occupiable;
        private final boolean diagonal;
        private final char type; // space ' ' for wall, dot '.' for room, sign '+' for corridor

        public Land(char type) {
            this.type = type;
            if (type == '+') {
                occupiable = true;
                diagonal = false;
            } else if (type == '.') {
                occupiable = true;
                diagonal = true;
            } else if (type == ' ') {
                occupiable = false;
                diagonal = false;
            } else {
                System.out.println("Error loading map: " + type);
                occupiable = false;
                diagonal = false;
            }
        }

        public char getType() {
            return type;
        }

        public Land copy() {
            return new Land(type);
        }

        public boolean orthogonalMoveable(Land land) {
            return occupiable && land.occupiable;
        }

        public boolean diagonalMoveable(Land land) {
            return diagonal && land.diagonal;
        }

    }

}